package datastructure;

/**
 * amortized O(logn) for operation, tested
 * 
 * @author yinzichen
 * 
 * @param <T>
 */
public class Splay<T extends Comparable<T>> {

	class Node {
		T val;
		Node p;
		Node lc;
		Node rc;

		public Node(T v) {
			val = v;
			p = null;
			lc = null;
			rc = null;
		}
	}

	private Node root;

	public Splay() {
		root = null;
	}

	public void add(T val) {
		Node newNode = new Node(val);
		if (root == null) {
			root = newNode;
			return;
		}
		Node cur = root;
		while (true) {
			if (cur.val.compareTo(val) > 0) {
				if (cur.lc == null) {
					cur.lc = newNode;
					break;
				} else {
					cur = cur.lc;
				}
			} else {
				if (cur.rc == null) {
					cur.rc = newNode;
					break;
				} else {
					cur = cur.rc;
				}
			}
		}
		newNode.p = cur;
		splay(newNode);
	}

	/**
	 * remove the first Node found with value val
	 * 
	 * @param val
	 *            the value to be removed
	 * @return true if the val exist or false
	 */
	public boolean remove(T val) {
		Node node = _find(val);
		if (node == null) {
			return false;
		}
		if (node.val.compareTo(val) != 0) {
			splay(node);
			return false;
		}
		Node p = remove(node);
		if (p != null) {
			splay(p);
		}
		return true;
	}

	public T find(T val) {
		Node node = _find(val);
		if (node == null) {
			return null;
		}
		splay(node);
		// if (node.val.compareTo(val) != 0) {
		// return null;
		// }
		return node.val;
	}

	public boolean isEmpty() {
		return root == null;
	}

	/**
	 * remove the node by its reference
	 * 
	 * @param node
	 *            the reference of the node to be removed
	 * @return its parent or null if it is root
	 */
	private Node remove(Node node) {
		Node subRoot = null;
		if (node.lc != null && node.rc != null) {
			subRoot = predecessor(node);
			remove(subRoot);
			subRoot.lc = node.lc;
			if (subRoot.lc != null) {
				subRoot.lc.p = subRoot;
			}
			subRoot.rc = node.rc;
			subRoot.rc.p = subRoot;
			subRoot.p = node.p;
		} else if (node.lc != null || node.rc != null) {
			subRoot = node.lc == null ? node.rc : node.lc;
			subRoot.p = node.p;
		}
		if (node == root) {
			root = subRoot;
		} else if (node.p.lc == node) {
			node.p.lc = subRoot;
		} else {
			node.p.rc = subRoot;
		}
		return node.p;
	}

	/**
	 * find the first Node with value val
	 * 
	 * @param val
	 *            the value to look up
	 * @return the Node with value val or the last Node accessed
	 */
	private Node _find(T val) {
		Node cur = root;
		Node last = null;
		while (cur != null) {
			last = cur;
			if (cur.val.compareTo(val) == 0) {
				return cur;
			} else if (cur.val.compareTo(val) > 0) {
				cur = cur.lc;
			} else {
				cur = cur.rc;
			}
		}
		return last;
	}

	/**
	 * rotate the node to root by its reference
	 * 
	 * @param cur
	 *            the reference of the node to be rotated
	 */
	private void splay(Node cur) {
		while (cur != root) {
			boolean isLeft = cur.p.lc == cur ? true : false;
			boolean isPLeft = cur.p.p == null || cur.p.p.rc == cur.p ? false
					: true;
			boolean isPRight = cur.p.p == null || cur.p.p.lc == cur.p ? false
					: true;
			if (isLeft) {
				if (isPLeft) {
					rotateRight(cur.p.p);
				}
				rotateRight(cur.p);
			} else {
				if (isPRight) {
					rotateLeft(cur.p.p);
				}
				rotateLeft(cur.p);
			}
		}
	}

	private void rotateLeft(Node cur) {
		cur.rc.p = cur.p;
		if (cur.p != null) {
			if (cur.p.lc == cur) {
				cur.p.lc = cur.rc;
			} else {
				cur.p.rc = cur.rc;
			}
		} else {
			root = cur.rc;
		}
		Node tmp = cur.rc;
		if (tmp.lc != null) {
			tmp.lc.p = cur;
		}
		cur.rc = cur.rc.lc;
		tmp.lc = cur;
		cur.p = tmp;
	}

	private void rotateRight(Node cur) {
		cur.lc.p = cur.p;
		if (cur.p != null) {
			if (cur.p.lc == cur) {
				cur.p.lc = cur.lc;
			} else {
				cur.p.rc = cur.lc;
			}
		} else {
			root = cur.lc;
		}
		Node tmp = cur.lc;
		if (tmp.rc != null) {
			tmp.rc.p = cur;
		}
		cur.lc = cur.lc.rc;
		tmp.rc = cur;
		cur.p = tmp;
	}

	private Node predecessor(Node node) {
		if (node.lc == null)
			return null;
		Node res = node.lc;
		while (res.rc != null) {
			res = res.rc;
		}
		return res;
	}

}